package edu.dayu.demo4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释: 变位词 指字母相同的
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。
 *
 * 思路：基本思路，如果 时变位词 ad 和 da 的和相等，但是为了避免 bc 这样的情况，将每个值都变成立方加求和，这样出错的概率就会非常小。
 *      基于以上思路，利用前缀和，拿到 s 的所有和存入一个数组。
 *      然后每次 sum【i】-sum【j】 i-j = p.len 来与 p 比较即可。
 *      时间复杂度 o（n）
 *
 */
public class 字符串中的所有变位词 {
    public static void main(String[] args) {
        String s = "aa";
        String p = "bb";
        System.out.println(findAnagrams(s, p));
    }

    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        long sum = 0;
        for (int i = 0; i < p.length(); i++) {
            sum += (long) Math.pow(p.charAt(i)-'a',3);
        }
        long[] sums = new long[s.length()+1];
        sums[0] = 0;
        for (int i = 0; i < s.length(); i++) {
            sums[i+1] = (long) Math.pow(s.charAt(i)-'a',3)+sums[i];
        }
        for (int i = p.length(),j=0; i <= s.length(); i++,j++) {
            if (sums[i]==sums[j]+sum){
                list.add(j);
            }
        }
        return list;
    }
}
